#!/usr/bin/env python
# -*- coding: utf-8 -*-

import os
import sys
sys.path.append(os.path.join(os.path.dirname(__file__), '..'))
import utils.rand_kit as rand_kit

import random

# 归并排序，复杂度O(n * log(2)n)
def merge_sort_scoped(arr, left, right):
    if(left >= right): return

    mid = (left + right) / 2
    merge_sort_scoped(arr, left, mid)
    merge_sort_scoped(arr, mid + 1, right)
    lptr = left
    rptr = mid + 1
    tmp_arr = []
    while(lptr <= mid or rptr <= right):
        if(rptr > right or lptr <= mid and arr[lptr] <= arr[rptr]):
            tmp_arr.append(arr[lptr])
            lptr += 1
        else:
            tmp_arr.append(arr[rptr])
            rptr += 1
    for i in range(left, right + 1):
        arr[i] = tmp_arr[i - left]

def merge_sort(arr):
    merge_sort_scoped(arr, 0, len(arr) - 1)

if __name__ == "__main__":
    arr = rand_kit.rand_arr()
    merge_sort(arr)
    print(arr)